package com.zac.coroutine.algorithm.leetcode.linkedlist



/**
 * author zac
 * date 2025/8/2
 *给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 */
object ReverseList {
    @JvmStatic
    fun main(args: Array<String>) {

        val n5 = ListNode(null,5)
        val n4 = ListNode(n5,4)
        val n3 = ListNode(n4,3)
        val n2 = ListNode(n3,2)
        val n1 = ListNode(n2,1)
        reverseList(n1)

    }

    fun reverseList(head: ListNode?): ListNode? {
        if (head == null) return null
        return getNewHead(null, head)
    }

    /**
     * 迭代解法
     */
    fun reverseList1(head: ListNode?): ListNode? {
        var prev: ListNode? = null
        var curr = head
        while (curr != null) {
            val next = curr.next
            curr.next = prev
            prev = curr
            curr = next
        }
        return prev
    }


    /**
     * 递归解法
     */
    fun getNewHead(lastNode: ListNode?, node: ListNode): ListNode {

        val realNext = node.next

        if (realNext == null) {
            node.next = lastNode
            return node
        }
        if (lastNode != null) {
            node.next = lastNode
        }else{
            node.next = null
        }
        return getNewHead(node, realNext)
    }
}